#include<cstdio>
#include<cstring>
const int maxn=200010;
const int MAXINT=0xfffffff;
struct node
{
	int left,right;
	int max,add;
}tree[maxn*4];
int n,t,m,k,a[maxn],f[maxn];
int max(int x,int y)
{
	return x>y?x:y;
}
void PushUp(int u)
{
	tree[u].max=max(tree[u*2].max,tree[u*2+1].max);
}
void PushDown(int u)
{
	tree[u*2].max+=tree[u].add;
	tree[u*2+1].max+=tree[u].add;
	tree[u*2].add+=tree[u].add;
	tree[u*2+1].add+=tree[u].add;
	tree[u].add=0;
}
void build(int u,int L,int R)
{
	tree[u].left=L;
	tree[u].right=R;
	tree[u].add=0;
	if(L==R){tree[u].max=f[L];return;}
	int mid=(L+R)/2;
	build(u*2,L,mid);
	build(u*2+1,mid+1,R);
	tree[u].max=max(tree[u*2].max,tree[u*2+1].max);
}
void update(int u,int L,int R,int add)
{
	if(L<=tree[u].left&&R>=tree[u].right)
	{
		tree[u].add+=add;
		tree[u].max+=add;
		return;
	}
	if(tree[u].add)
		PushDown(u);
	int mid=(tree[u].left+tree[u].right)/2;
	if(L<=mid)update(u*2,L,R,add);
	if(R>mid)update(u*2+1,L,R,add);
	PushUp(u);
}
int query(int u,int L,int R)
{
	if(L<=tree[u].left&&R>=tree[u].right)return tree[u].max;
	if(tree[u].add)
		PushDown(u);
	int i=-MAXINT,j=-MAXINT;
	int mid=(tree[u].left+tree[u].right)/2;
	if(L<=mid)i=query(u*2,L,R);
	if(R>mid)j=query(u*2+1,L,R);
	return max(i,j);
}
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		memset(f,0,sizeof(f));
		scanf("%d%d%d",&n,&m,&k);
		for(int i=1;i<=n;i++)
			scanf("%d",&a[i]);
		for(int i=1;i<=k;i++)f[1]+=a[i];
		for(int i=2;i<=n-k+1;i++)
			f[i]=f[i-1]-a[i-1]+a[i+k-1];
		build(1,1,n-k+1);
		for(int i=1;i<=m;i++)
		{
			int x,y,p;
			scanf("%d%d%d",&p,&x,&y);
			if(p==0)
			{
				update(1,max(x-k+1,1),x,y-a[x]);
				a[x]=y;
			}
			if(p==1)
			{
				int t=a[x];
				update(1,max(x-k+1,1),x,a[y]-a[x]);
				a[x]=a[y];
				update(1,max(y-k+1,1),y,t-a[y]);
				a[y]=t;
			}
			if(p==2)printf("%d\n",query(1,x,y-k+1));
		}
	}
	return 0;
}
			


